{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum Building Height"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #math"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #数学"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxBuilding"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最高建筑高度"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>在一座城市里，你需要建 <code>n</code> 栋新的建筑。这些新的建筑会从 <code>1</code> 到 <code>n</code> 编号排成一列。</p>\n",
    "\n",
    "<p>这座城市对这些新建筑有一些规定：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>每栋建筑的高度必须是一个非负整数。</li>\n",
    "\t<li>第一栋建筑的高度 <strong>必须</strong> 是 <code>0</code> 。</li>\n",
    "\t<li>任意两栋相邻建筑的高度差 <strong>不能超过</strong>  <code>1</code> 。</li>\n",
    "</ul>\n",
    "\n",
    "<p>除此以外，某些建筑还有额外的最高高度限制。这些限制会以二维整数数组 <code>restrictions</code> 的形式给出，其中 <code>restrictions[i] = [id<sub>i</sub>, maxHeight<sub>i</sub>]</code> ，表示建筑 <code>id<sub>i</sub></code> 的高度 <strong>不能超过</strong> <code>maxHeight<sub>i</sub></code> 。</p>\n",
    "\n",
    "<p>题目保证每栋建筑在 <code>restrictions</code> 中<strong> 至多出现一次</strong> ，同时建筑 <code>1</code> <strong>不会</strong> 出现在 <code>restrictions</code> 中。</p>\n",
    "\n",
    "<p>请你返回 <strong>最高</strong> 建筑能达到的 <strong>最高高度</strong> 。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2021/04/25/ic236-q4-ex1-1.png\" style=\"width: 400px; height: 253px;\" />\n",
    "<pre>\n",
    "<b>输入：</b>n = 5, restrictions = [[2,1],[4,1]]\n",
    "<b>输出：</b>2\n",
    "<b>解释：</b>上图中的绿色区域为每栋建筑被允许的最高高度。\n",
    "我们可以使建筑高度分别为 [0,1,2,1,2] ，最高建筑的高度为 2 。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2021/04/25/ic236-q4-ex2.png\" style=\"width: 500px; height: 269px;\" />\n",
    "<pre>\n",
    "<b>输入：</b>n = 6, restrictions = []\n",
    "<b>输出：</b>5\n",
    "<b>解释：</b>上图中的绿色区域为每栋建筑被允许的最高高度。\n",
    "我们可以使建筑高度分别为 [0,1,2,3,4,5] ，最高建筑的高度为 5 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2021/04/25/ic236-q4-ex3.png\" style=\"width: 500px; height: 187px;\" />\n",
    "<pre>\n",
    "<b>输入：</b>n = 10, restrictions = [[5,3],[2,5],[7,4],[10,3]]\n",
    "<b>输出：</b>5\n",
    "<b>解释：</b>上图中的绿色区域为每栋建筑被允许的最高高度。\n",
    "我们可以使建筑高度分别为 [0,1,2,3,3,4,4,5,4,3] ，最高建筑的高度为 5 。\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>2 <= n <= 10<sup>9</sup></code></li>\n",
    "\t<li><code>0 <= restrictions.length <= min(n - 1, 10<sup>5</sup>)</code></li>\n",
    "\t<li><code>2 <= id<sub>i</sub> <= n</code></li>\n",
    "\t<li><code>id<sub>i</sub></code> 是 <strong>唯一的</strong> 。</li>\n",
    "\t<li><code>0 <= maxHeight<sub>i</sub> <= 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-building-height](https://leetcode.cn/problems/maximum-building-height/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-building-height](https://leetcode.cn/problems/maximum-building-height/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['5\\n[[2,1],[4,1]]', '6\\n[]', '10\\n[[5,3],[2,5],[7,4],[10,3]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxBuilding(self, n: int, restrictions: List[List[int]]) -> int:\n",
    "        #h - h1 + h - h2 <= j-i\n",
    "        if len(restrictions) == 0:\n",
    "            return n-1\n",
    "        restrictions.sort(key = lambda x:x[0])\n",
    "        for i in range(len(restrictions)-1,0,-1):\n",
    "            if restrictions[i][0] - restrictions[i-1][0] < restrictions[i-1][1] - restrictions[i][1]:\n",
    "                restrictions[i-1][1] = restrictions[i][1] + restrictions[i][0] - restrictions[i-1][0] \n",
    "\n",
    "        begin = 1\n",
    "        current = 0\n",
    "        maxHeight = 0\n",
    "        for restriction in restrictions:\n",
    "            end = restriction[0]\n",
    "            if end - begin > abs(restriction[1] - current):\n",
    "                maxHeight = max((end - begin + current + restriction[1])//2, maxHeight)\n",
    "                begin = end\n",
    "                current = restriction[1]\n",
    "            else:\n",
    "                if restriction[1] > current:\n",
    "                    current += end - begin\n",
    "                    begin = end\n",
    "                    maxHeight = max(current, maxHeight)\n",
    "                else:\n",
    "                    current = restriction[1]\n",
    "                    begin = end\n",
    "        maxHeight = max(current + n - begin,maxHeight)        \n",
    "        return maxHeight\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxBuilding(self, n: int, restrictions: List[List[int]]) -> int:\n",
    "        restrictions.sort()\n",
    "        res, m = [[1,0]], len(restrictions)\n",
    "        for i in range(m):\n",
    "            inx, h = restrictions[i]\n",
    "            if h - res[-1][1] >= inx - res[-1][0]: continue\n",
    "            while res[-1][1] - h >= inx - res[-1][0]: res.pop()\n",
    "            res.append([inx,h])\n",
    "        x, y, ans = 1, 0, n - res[-1][0] + res[-1][1]\n",
    "        for i, j in res: ans, x, y = max(ans, (j + y + i - x) // 2), i, j\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxBuilding(self, n: int, restrictions: List[List[int]]) -> int:\n",
    "        restrictions.sort()\n",
    "        m = len(restrictions)\n",
    "        for i in range(m-2, -1, -1):\n",
    "            a, h = restrictions[i+1]\n",
    "            restrictions[i][1] = min(restrictions[i][1], h + a-restrictions[i][0])\n",
    "        \n",
    "        ans = 0\n",
    "        a, h = 1, 0\n",
    "        for b,x in restrictions:\n",
    "            h2 = min(x, h + b-a)\n",
    "            z = b-a - abs(h - h2)\n",
    "            ans = max(ans, h2, max(h, h2) + z//2)\n",
    "            a, h = b, h2\n",
    "        \n",
    "        ans = max(ans, h + n-a)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxBuilding(self, n: int, restrictions: List[List[int]]) -> int:\n",
    "        restrictions.append([0,0])\n",
    "        restrictions.append([n,n-1])\n",
    "        restrictions.sort()\n",
    "        n=len(restrictions)\n",
    "        for i in range(1,n):\n",
    "            restrictions[i][1]=min(restrictions[i][1],restrictions[i-1][1]+restrictions[i][0]-restrictions[i-1][0],restrictions[i][0]-1)\n",
    "        for i in range(n-2,-1,-1):\n",
    "            restrictions[i][1]=min(restrictions[i][1],restrictions[i+1][1]-restrictions[i][0]+restrictions[i+1][0],restrictions[i][0]-1)\n",
    "        ret=0\n",
    "        for i in range(n-1):\n",
    "            ret=max(ret,(restrictions[i+1][0]-restrictions[i][0]+restrictions[i][1]+restrictions[i+1][1])//2)\n",
    "        #print(restrictions)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxBuilding(self, n: int, restrictions: List[List[int]]) -> int:\n",
    "        s = [(1, 0)]\n",
    "        restrictions.sort(key = lambda x: x[0])\n",
    "        for idx, mh in restrictions:\n",
    "            while mh < s[-1][1] and s[-1][1] - mh > idx - s[-1][0]:\n",
    "                s.pop(-1)\n",
    "            if mh > s[-1][1] and mh - s[-1][1] > idx - s[-1][0]:\n",
    "                pass\n",
    "            else:\n",
    "                s.append((idx, mh))\n",
    "        preid = 1\n",
    "        preh = 0\n",
    "        ans = 0\n",
    "        for item in s:\n",
    "            i, h = item[0], item[1]\n",
    "            # print((i, h))\n",
    "            t = max(preh, h) + (i - preid - abs(preh - h)) // 2\n",
    "            ans = max(ans, t)\n",
    "            preid, preh = i, h\n",
    "        ans = max(ans, preh + n - preid)\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxBuilding(self, n: int, restrictions: List[List[int]]) -> int:\n",
    "        restrictions.append([1, 0])\n",
    "        restrictions.sort()\n",
    "        if restrictions[-1][0] != n:\n",
    "            restrictions.append([n, n - 1])\n",
    "        else:\n",
    "            restrictions[-1][1] = min(n - 1, restrictions[-1][1])\n",
    "        m = len(restrictions)\n",
    "        for i in range(1, m):\n",
    "            if (dx := restrictions[i][0] - restrictions[i - 1][0]) <= (dy := restrictions[i][1] - restrictions[i - 1][1]) and dy >= 0:\n",
    "                restrictions[i][1] = restrictions[i - 1][1] + dx\n",
    "            elif dx <= -dy:\n",
    "                restrictions[i - 1][1] = restrictions[i][1] + dx\n",
    "        for i in range(m - 1, 0, -1):\n",
    "            if (dx := restrictions[i][0] - restrictions[i - 1][0]) <= (dy := restrictions[i][1] - restrictions[i - 1][1]) and dy >= 0:\n",
    "                restrictions[i][1] = restrictions[i - 1][1] + dx\n",
    "            elif dx <= -dy:\n",
    "                restrictions[i - 1][1] = restrictions[i][1] + dx\n",
    "        return max(restrictions[i][1] + ((restrictions[i][0] - restrictions[i - 1][0] - (restrictions[i][1] - restrictions[i - 1][1])) >> 1) if restrictions[i][1] >= restrictions[i - 1][1] else restrictions[i - 1][1] + ((restrictions[i][0] - restrictions[i - 1][0] + restrictions[i][1] - restrictions[i - 1][1]) >> 1) for i in range(1, m))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxBuilding(self, n: int, restrictions: List[List[int]]) -> int:\n",
    "        restrictions.append([1, 0])\n",
    "        restrictions.sort()\n",
    "        if restrictions[-1][0] != n:\n",
    "            restrictions.append([n, n-1])\n",
    "        m = len(restrictions)\n",
    "\n",
    "        for i in range(1, m):\n",
    "            a = restrictions[i][1]\n",
    "            b = restrictions[i-1][1] + restrictions[i][0] - restrictions[i-1][0]\n",
    "            restrictions[i][1] = a if a < b else b\n",
    "\n",
    "        for i in range(m - 2, -1, -1):\n",
    "            a = restrictions[i][1]\n",
    "            b = restrictions[i + 1][1] + restrictions[i + 1][0] - restrictions[i][0]\n",
    "            restrictions[i][1] = a if a < b else b\n",
    "\n",
    "        ans = 0\n",
    "        for i in range(1, m):\n",
    "            a = restrictions[i - 1][1]\n",
    "            b = restrictions[i][1]\n",
    "            if b > ans:\n",
    "                ans = b\n",
    "            mid = (a+b+restrictions[i][0]-restrictions[i-1][0]) // 2\n",
    "            if mid > ans:\n",
    "                ans = mid\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def maxBuilding(self, n: int, r: List[List[int]]) -> int:\n",
    "        r.append([1,0])\n",
    "        r.sort()\n",
    "        \n",
    "        if r[-1][0]!=n:\n",
    "            r.append([n, n-1])\n",
    "        \n",
    "        m = len(r)\n",
    "        for i in range(1, m):\n",
    "            r[i][1] = min(r[i][1], r[i-1][1]+(r[i][0]-r[i-1][0]))\n",
    "        for i in range(m-2, 0, -1):\n",
    "            r[i][1] = min(r[i][1], r[i+1][1]+(r[i+1][0]-r[i][0]))\n",
    "        ans = 0\n",
    "        for i in range(m-1):\n",
    "            best = (r[i][1]+r[i+1][1]+(r[i+1][0]-r[i][0]))//2\n",
    "            ans = max(ans, best)\n",
    "        return ans\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxBuilding(self, n: int, restrictions: List[List[int]]) -> int:\n",
    "        restrictions.sort()#按编号排序\n",
    "        res = 0\n",
    "        stack = [[1, 0]]#单调栈\n",
    "        for i, h in restrictions:\n",
    "            while stack[-1][1] - (i - stack[-1][0]) > h: #如果左侧高度超标,弹出\n",
    "                stack.pop()\n",
    "            stack.append([i, min(h, stack[-1][1] + i - stack[-1][0])]) #限制右侧的最大高度并入栈\n",
    "        res = 0\n",
    "        for i in range(1, len(stack)):#依次遍历\n",
    "            res = max(res, (stack[i][1] + stack[i - 1][1] + (stack[i][0] - stack[i - 1][0])) // 2) #通过上面的公式求最大值\n",
    "        if stack[-1][0] < n:#考虑栈中最后元素的情况\n",
    "            res = max(res, n - stack[-1][0] + stack[-1][1])\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxBuilding(self, n: int, restrictions: List[List[int]]) -> int:\n",
    "        s = restrictions\n",
    "        s.extend([[1, 0], [n, n - 1]])\n",
    "        m = len(s)\n",
    "        s.sort()\n",
    "\n",
    "        for i in range(1, m):\n",
    "            s[i][1] = min(s[i][1], s[i - 1][1] + s[i][0] - s[i - 1][0])\n",
    "        for i in range(m - 2, -1, -1):\n",
    "            s[i][1] = min(s[i][1], s[i + 1][1] + s[i + 1][0] - s[i][0])\n",
    "        \n",
    "        ans = 0\n",
    "        for (x, h1), (y, h2) in pairwise(s):\n",
    "            ans = max(ans, (h1 + y + h2 - x) // 2)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxBuilding(self, n: int, restrictions: List[List[int]]) -> int:\n",
    "        restrictions.sort()#按编号排序\n",
    "        res = 0\n",
    "        stack = [[1, 0]]#单调栈\n",
    "        for i, h in restrictions:\n",
    "            while stack[-1][1] - (i - stack[-1][0]) > h: #如果左侧高度超标,弹出\n",
    "                stack.pop()\n",
    "            stack.append([i, min(h, stack[-1][1] + i - stack[-1][0])]) #限制右侧的最大高度并入栈\n",
    "        res = 0\n",
    "        for i in range(1, len(stack)):#依次遍历\n",
    "            res = max(res, (stack[i][1] + stack[i - 1][1] + (stack[i][0] - stack[i - 1][0])) // 2) #通过上面的公式求最大值\n",
    "        if stack[-1][0] < n:#考虑栈中最后元素的情况\n",
    "            res = max(res, n - stack[-1][0] + stack[-1][1])\n",
    "        return res\n",
    "        '''\n",
    "        restrictions.append([1,0])\n",
    "        restrictions.sort(key = lambda x: x[0])\n",
    "        if restrictions[-1][0] != n:\n",
    "            restrictions.append([n,1e9])\n",
    "        m = len(restrictions)\n",
    "        pid, pmh = 1, 0\n",
    "        for i in range(1,m):\n",
    "            id_, mh_ = restrictions[i-1]\n",
    "            idi, mhi = restrictions[i]\n",
    "            if mhi > mh_ + idi - id_:\n",
    "                restrictions[i][1] = mh_ + idi - id_\n",
    "        for i in range(m-2,0,-1):\n",
    "            id_, mh_ = restrictions[i+1]\n",
    "            idi, mhi = restrictions[i]\n",
    "            if mhi > mh_ + id_ - idi:\n",
    "                restrictions[i][1] = mh_ + id_ - idi\n",
    "        res = 0\n",
    "        for i in range(1,m):\n",
    "            id_, mh_ = restrictions[i-1]\n",
    "            idi, mhi = restrictions[i]\n",
    "            res = max(res, (idi - id_ + mh_ + mhi) // 2)\n",
    "        #print(restrictions)\n",
    "        return res\n",
    "        '''\n",
    "        '''\n",
    "        restr = [-1 for _ in range(n)]\n",
    "        restr[0] = 0\n",
    "        for i, mh in restrictions:\n",
    "            restr[i-1] = mh\n",
    "        p=1\n",
    "        while p<n:\n",
    "            if restr[p] != -1 and restr[p] < restr[p-1]+1:\n",
    "                q = p - 1\n",
    "                while q>0:\n",
    "                    if restr[q] > restr[q+1] + 1:\n",
    "                        restr[q] = restr[q+1] + 1\n",
    "                        q -= 1\n",
    "                    else:\n",
    "                        break\n",
    "            else:\n",
    "                restr[p] = restr[p-1]+1\n",
    "            p += 1\n",
    "        return max(restr)\n",
    "        '''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxBuilding(self, n: int, restrictions: List[List[int]]) -> int:\n",
    "        restrictions.append([1, 0])\n",
    "        restrictions.sort()\n",
    "        if restrictions[-1][0] != n:\n",
    "            restrictions.append([n, n - 1])\n",
    "        m = len(restrictions)\n",
    "        for i in range(1, m):\n",
    "            restrictions[i][1] = min(restrictions[i][1], restrictions[i - 1][1] + (restrictions[i][0] - restrictions[i - 1][0]))\n",
    "        for i in range(m - 1, 0, -1):\n",
    "            restrictions[i - 1][1] = min(restrictions[i - 1][1], restrictions[i][1] + (restrictions[i][0] - restrictions[i - 1][0]))\n",
    "        return max((restrictions[i][0] - restrictions[i - 1][0] + restrictions[i][1] + restrictions[i - 1][1]) >> 1 for i in range(1, m))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxBuilding(self, n: int, restrictions: List[List[int]]) -> int:\n",
    "        restrictions.sort()#按编号排序\n",
    "        res = 0\n",
    "        stack = [[1, 0]]#单调栈\n",
    "        for i, h in restrictions:\n",
    "            while stack[-1][1] - (i - stack[-1][0]) > h: #如果左侧高度超标,弹出\n",
    "                stack.pop()\n",
    "            stack.append([i, min(h, stack[-1][1] + i - stack[-1][0])]) #限制右侧的最大高度并入栈\n",
    "        res = 0\n",
    "        for i in range(1, len(stack)):#依次遍历\n",
    "            res = max(res, (stack[i][1] + stack[i - 1][1] + (stack[i][0] - stack[i - 1][0])) // 2) #通过上面的公式求最大值\n",
    "        if stack[-1][0] < n:#考虑栈中最后元素的情况\n",
    "            res = max(res, n - stack[-1][0] + stack[-1][1])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxBuilding(self, n: int, restrictions: List[List[int]]) -> int:\n",
    "        restrictions.append([1, 0])\n",
    "        restrictions.append([n, n - 1])\n",
    "        restrictions.sort()\n",
    "        m = len(restrictions)\n",
    "        for i in range(1, m):\n",
    "            restrictions[i][1] = min(restrictions[i][1], restrictions[i - 1][1] + restrictions[i][0] - restrictions[i - 1][0])\n",
    "        for i in range(m - 2, -1, -1):\n",
    "            restrictions[i][1] = min(restrictions[i][1], restrictions[i + 1][1] + restrictions[i + 1][0] - restrictions[i][0])\n",
    "        ans = 0\n",
    "        for i in range(1, m):\n",
    "            left, right = restrictions[i - 1], restrictions[i]\n",
    "            ans = max(ans, (left[1] + right[1] + right[0] - left[0]) // 2)\n",
    "        return ans\n",
    "    \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxBuilding(self, n: int, restrictions: List[List[int]]) -> int:\n",
    "        restrictions.append([1, 0])\n",
    "        restrictions.sort()\n",
    "        if restrictions[-1][0] != n:\n",
    "            restrictions.append([n, n - 1])\n",
    "        else:\n",
    "            restrictions[-1][1] = min(n - 1, restrictions[-1][1])\n",
    "        m = len(restrictions)\n",
    "        for i in range(1, m):\n",
    "            if (dx := restrictions[i][0] - restrictions[i - 1][0]) <= (dy := restrictions[i][1] - restrictions[i - 1][1]) and restrictions[i][1] >= restrictions[i - 1][1]:\n",
    "                restrictions[i][1] = restrictions[i - 1][1] + dx\n",
    "            elif dx <= -dy:\n",
    "                restrictions[i - 1][1] = restrictions[i][1] + dx\n",
    "        for i in range(m - 1, 0, -1):\n",
    "            if (dx := restrictions[i][0] - restrictions[i - 1][0]) <= (dy := restrictions[i][1] - restrictions[i - 1][1]) and restrictions[i][1] >= restrictions[i - 1][1]:\n",
    "                restrictions[i][1] = restrictions[i - 1][1] + dx\n",
    "            elif dx <= -dy:\n",
    "                restrictions[i - 1][1] = restrictions[i][1] + dx\n",
    "        return max(restrictions[i][1] + ((restrictions[i][0] - restrictions[i - 1][0] - (restrictions[i][1] - restrictions[i - 1][1])) >> 1) if restrictions[i][1] >= restrictions[i - 1][1] else restrictions[i - 1][1] + ((restrictions[i][0] - restrictions[i - 1][0] + restrictions[i][1] - restrictions[i - 1][1]) >> 1) for i in range(1, m))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxBuilding(self, n: int, restrictions: List[List[int]]) -> int:\n",
    "        restrictions.append([1,0])\n",
    "        restrictions.sort()\n",
    "        if restrictions[-1][0]!=n:\n",
    "            restrictions.append([n,n-1])\n",
    "        # 扩散限制\n",
    "        for i in range(1, len(restrictions)):\n",
    "            restrictions[i][1]=min(restrictions[i][1], restrictions[i-1][1]+restrictions[i][0]-restrictions[i-1][0])\n",
    "        for i in range(len(restrictions)-2, 0,-1):\n",
    "            restrictions[i][1]=min(restrictions[i][1], restrictions[i+1][1]+restrictions[i+1][0]-restrictions[i][0])\n",
    "        ans=0\n",
    "        for i in range(1, len(restrictions)):\n",
    "            ans=max(ans, (restrictions[i][0]-restrictions[i-1][0]+restrictions[i][1]+restrictions[i-1][1])//2)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxBuilding(self, n: int, restrictions: List[List[int]]) -> int:\n",
    "        r = restrictions\n",
    "        # 增加限制 (1, 0)\n",
    "        r.append([1, 0])\n",
    "        r.sort()\n",
    "\n",
    "        # 增加限制 (n, n-1)\n",
    "        if r[-1][0] != n:\n",
    "            r.append([n, n - 1])\n",
    "\n",
    "        m = len(r)\n",
    "        \n",
    "        # 从左向右传递限制\n",
    "        for i in range(1, m):\n",
    "            r[i][1] = min(r[i][1], r[i - 1][1] + (r[i][0] - r[i - 1][0]))\n",
    "        # 从右向左传递限制\n",
    "        for i in range(m - 2, 0, -1):\n",
    "            r[i][1] = min(r[i][1], r[i + 1][1] + (r[i + 1][0] - r[i][0]))\n",
    "            \n",
    "        ans = 0\n",
    "        for i in range(m - 1):\n",
    "            # 计算 r[i][0] 和 r[i][1] 之间的建筑的最大高度\n",
    "            best = ((r[i + 1][0] - r[i][0]) + r[i][1] + r[i + 1][1]) // 2\n",
    "            ans = max(ans, best)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxBuilding(self, n: int, restrictions: List[List[int]]) -> int:\n",
    "        restrictions.append([1, 0])\n",
    "        restrictions.sort(key=lambda x: x[0])\n",
    "        m = len(restrictions)\n",
    "        for i in range(1, m):\n",
    "            h = restrictions[i-1][1] + restrictions[i][0] - restrictions[i-1][0]\n",
    "            if restrictions[i][1] > h:\n",
    "                restrictions[i][1] = h\n",
    "        for i in reversed(range(m-1)):\n",
    "            h = restrictions[i+1][1] + restrictions[i+1][0] - restrictions[i][0]\n",
    "            if restrictions[i][1] > h:\n",
    "                restrictions[i][1] = h\n",
    "        res = restrictions[m-1][1] + n - restrictions[m-1][0]\n",
    "        for i in range(m-1):\n",
    "            res = max(res, (restrictions[i][1] + restrictions[i+1]\n",
    "                      [1] + restrictions[i+1][0] - restrictions[i][0]) // 2)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxBuilding(self, n: int, restrictions: List[List[int]]) -> int:\n",
    "        r1 = -1\n",
    "        restrictions.sort()\n",
    "        st = [inf]\n",
    "        for i, h in reversed(restrictions):\n",
    "            if i + h < st[-1]:\n",
    "                st.append(i + h)\n",
    "            else:\n",
    "                st.append(st[-1])\n",
    "        \n",
    "        l, ans = 1, 0\n",
    "        for x, h in restrictions:\n",
    "            r2 = st.pop()\n",
    "            z = (r2 - r1) // 2\n",
    "            if z > x:\n",
    "                max_h = x + r1\n",
    "            elif z < l:\n",
    "                max_h = -x + r2\n",
    "            else:\n",
    "                max_h = z + r1\n",
    "            ans = max(ans, max_h)\n",
    "            r1 = min(h-x, r1)\n",
    "            l = x\n",
    "        return max(ans, n+r1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxBuilding(self, n: int, restrictions: List[List[int]]) -> int:\n",
    "        restrictions.append([1,0])\n",
    "        restrictions.sort(key = lambda x: x[0])\n",
    "        if restrictions[-1][0] != n:\n",
    "            restrictions.append([n,1e9])\n",
    "        m = len(restrictions)\n",
    "        pid, pmh = 1, 0\n",
    "        for i in range(1,m):\n",
    "            id_, mh_ = restrictions[i-1]\n",
    "            idi, mhi = restrictions[i]\n",
    "            if mhi > mh_ + idi - id_:\n",
    "                restrictions[i][1] = mh_ + idi - id_\n",
    "        for i in range(m-2,0,-1):\n",
    "            id_, mh_ = restrictions[i+1]\n",
    "            idi, mhi = restrictions[i]\n",
    "            if mhi > mh_ + id_ - idi:\n",
    "                restrictions[i][1] = mh_ + id_ - idi\n",
    "        res = 0\n",
    "        for i in range(1,m):\n",
    "            id_, mh_ = restrictions[i-1]\n",
    "            idi, mhi = restrictions[i]\n",
    "            res = max(res, (idi - id_ + mh_ + mhi) // 2)\n",
    "        #print(restrictions)\n",
    "        return res\n",
    "        \n",
    "        '''\n",
    "        restr = [-1 for _ in range(n)]\n",
    "        restr[0] = 0\n",
    "        for i, mh in restrictions:\n",
    "            restr[i-1] = mh\n",
    "        p=1\n",
    "        while p<n:\n",
    "            if restr[p] != -1 and restr[p] < restr[p-1]+1:\n",
    "                q = p - 1\n",
    "                while q>0:\n",
    "                    if restr[q] > restr[q+1] + 1:\n",
    "                        restr[q] = restr[q+1] + 1\n",
    "                        q -= 1\n",
    "                    else:\n",
    "                        break\n",
    "            else:\n",
    "                restr[p] = restr[p-1]+1\n",
    "            p += 1\n",
    "        return max(restr)\n",
    "        '''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxBuilding(self, n: int, restrictions: List[List[int]]) -> int:\n",
    "        restrictions.append([1, 0])\n",
    "        restrictions.sort()\n",
    "        if not restrictions or restrictions[-1][0] != n:\n",
    "            restrictions.append([n, n - 1])\n",
    "        # 从左侧更新限高\n",
    "        for i in range(1, len(restrictions)):\n",
    "            t = restrictions[i - 1][1] + restrictions[i][0] - restrictions[i - 1][0]\n",
    "            if t < restrictions[i][1]:\n",
    "                restrictions[i][1] = t\n",
    "        # 从右侧更新限高\n",
    "        for i in range(len(restrictions) - 2, -1, -1):\n",
    "            t = restrictions[i + 1][1] + restrictions[i + 1][0] - restrictions[i][0]\n",
    "            if t < restrictions[i][1]:\n",
    "                restrictions[i][1] = t\n",
    "        # 从真实限高得到最大高度\n",
    "        res = 0\n",
    "        for (a, b), (c, d) in pairwise(restrictions):\n",
    "            if b > d:\n",
    "                b, d = d, b\n",
    "            t = d + (b + c - a - d) // 2\n",
    "            if t > res:\n",
    "                res = t\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxBuilding(self, n: int, restrictions: List[List[int]]) -> int:\n",
    "        restrictions.sort(key=lambda x:x[0])\n",
    "        q = deque()\n",
    "        for i, v in restrictions:\n",
    "            while q and q[-1][1] > v and q[-1][1] - v > i - q[-1][0]:\n",
    "                q.pop()\n",
    "            q.append([i, v])\n",
    "\n",
    "        ans = 0\n",
    "        x, y = 1, 0\n",
    "        while x < n:\n",
    "            while q and q[0][0] <= x:\n",
    "                q.popleft()\n",
    "            nx = q[0][0] if q else n\n",
    "            ny = min(nx - x + y, q[0][1]) if q else inf\n",
    "            l, r = 0, nx - x + y\n",
    "            while l < r:\n",
    "                mid = (l + r + 1) >> 1\n",
    "                if mid - y + mid - ny > nx - x:\n",
    "                    r = mid - 1\n",
    "                else:\n",
    "                    l = mid\n",
    "            ans = max(ans, l)\n",
    "            x, y = nx, ny\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxBuilding(self, n: int, restrictions: List[List[int]]) -> int:\n",
    "        r = restrictions\n",
    "        r.append([1, 0])\n",
    "        r.sort()\n",
    "        if r[-1][0] != n:\n",
    "            r.append([n, n-1])\n",
    "        m = len(r)\n",
    "        for i in range(1, m):\n",
    "            r[i][1] = min(r[i][1], r[i-1][1] + (r[i][0] - r[i-1][0]))\n",
    "        for i in range(m-2, 0, -1):\n",
    "            r[i][1] = min(r[i][1], r[i+1][1] + (r[i+1][0] - r[i][0]))\n",
    "        ans = 0\n",
    "        for i in range(m-1):\n",
    "            best = ((r[i+1][0] - r[i][0]) + r[i][1] + r[i+1][1]) // 2\n",
    "            ans = max(best, ans)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxBuilding(self, n: int, restrictions: List[List[int]]) -> int:\n",
    "        restrictions.append([1, 0])\n",
    "        restrictions.sort()\n",
    "        if restrictions[-1][0] != n:\n",
    "            restrictions.append([n, n-1])\n",
    "        for i in range(1, len(restrictions)):\n",
    "            restrictions[i][1] = min(restrictions[i][1], restrictions[i-1][1] + restrictions[i][0] - restrictions[i-1][0])\n",
    "        \n",
    "        for i in range(len(restrictions)-2, -1, -1):\n",
    "            restrictions[i][1] = min(restrictions[i][1], restrictions[i+1][1] + restrictions[i+1][0] - restrictions[i][0])\n",
    "\n",
    "\n",
    "        max_height = 0\n",
    "        for i in range(1, len(restrictions)):\n",
    "            tmp = (restrictions[i][0] - restrictions[i-1][0] + restrictions[i][1] + restrictions[i-1][1]) // 2\n",
    "            max_height = max(max_height, tmp)\n",
    "        \n",
    "        return max_height\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxBuilding(self, n: int, restrictions: List[List[int]]) -> int:\n",
    "        restrictions.append([1, 0])\n",
    "        restrictions.sort()\n",
    "        ans = 0\n",
    "        \n",
    "        if restrictions[-1][0] != n:\n",
    "            restrictions.append([n, n-1])\n",
    "        else:\n",
    "            restrictions[-1][1] = min(n-1, restrictions[-1][1])\n",
    "        \n",
    "        m = len(restrictions)\n",
    "        \n",
    "        for i in range(1, m):\n",
    "            dy = restrictions[i][1] - restrictions[i-1][1]\n",
    "            dx = restrictions[i][0] - restrictions[i-1][0]\n",
    "            if restrictions[i][1] >= restrictions[i-1][1]:\n",
    "                if dx <= dy:\n",
    "                    restrictions[i][1] = restrictions[i-1][1] + dx\n",
    "            else:\n",
    "                dy = -dy\n",
    "                if dx <= dy:\n",
    "                    restrictions[i-1][1] = restrictions[i][1] + dx\n",
    "        for i in range(m-1, 0, -1):\n",
    "            dy = restrictions[i][1] - restrictions[i-1][1]\n",
    "            dx = restrictions[i][0] - restrictions[i-1][0]\n",
    "            if restrictions[i][1] >= restrictions[i-1][1]:\n",
    "                if dx <= dy:\n",
    "                    restrictions[i][1] = restrictions[i-1][1] + dx\n",
    "            else:\n",
    "                dy = -dy\n",
    "                if dx <= dy:\n",
    "                    restrictions[i-1][1] = restrictions[i][1] + dx\n",
    "    \n",
    "        ans = 0\n",
    "        \n",
    "        for i in range(1, m):\n",
    "            dy = restrictions[i][1] - restrictions[i-1][1]\n",
    "            dx = restrictions[i][0] - restrictions[i-1][0]\n",
    "            if restrictions[i][1] >= restrictions[i-1][1]:\n",
    "                ans = max(ans, restrictions[i][1] + (dx - dy) // 2)\n",
    "            else:\n",
    "                dy = -dy\n",
    "                ans = max(ans, restrictions[i-1][1] + (dx - dy) // 2)\n",
    "                \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxBuilding(self, n: int, restrictions: List[List[int]]) -> int:\n",
    "        if not restrictions:\n",
    "            return n - 1\n",
    "        restrictions.sort()\n",
    "        dq = deque(restrictions)\n",
    "        res = deque()\n",
    "        pre = 1\n",
    "        while dq:\n",
    "            x, y = dq.popleft()\n",
    "            if x - y < pre:\n",
    "                y = x - pre \n",
    "            else:\n",
    "                pre = x - y\n",
    "            res.append([x, y])\n",
    "        ans = deque()\n",
    "        x, y = res.pop()\n",
    "        pre = x + y\n",
    "        ans.append([x, y])\n",
    "        while res:\n",
    "            x, y = res.pop()\n",
    "            if x + y > pre:\n",
    "                y = pre - x \n",
    "            pre = x + y \n",
    "            ans.append([x, y])\n",
    "        ans = list(ans)[::-1]\n",
    "        rnt = 0\n",
    "        ans = [[1, 0]] + ans \n",
    "        for pr, aft in pairwise(ans):\n",
    "            a, b = pr \n",
    "            x, y = aft \n",
    "            rnt = max(rnt, (b + y + x - a) // 2)\n",
    "        last_x, last_y = ans[-1]\n",
    "        rnt = max(rnt, last_y + n - last_x)\n",
    "        return rnt "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxBuilding(self, n: int, r: List[List[int]]) -> int:\n",
    "        \n",
    "        r.append([1, 0]) \n",
    "        r.sort()\n",
    "        if r[-1][0]!=n:\n",
    "            r.append([n, 10**10]) \n",
    "        print(r)\n",
    "        n = len(r)\n",
    "        left = {}\n",
    "        right = {}\n",
    "        for j in range(n)[::-1]:\n",
    "            if j==(n-1):\n",
    "                left[j] = r[j]\n",
    "            else:\n",
    "                if (left[j+1][1] + left[j+1][0] - r[j][0])<r[j][1]:\n",
    "                    left[j] = left[j+1] \n",
    "                else:\n",
    "                    left[j] = r[j] \n",
    "        for j in range(n):\n",
    "            if j==0:\n",
    "                right[j] = r[j]\n",
    "            else:\n",
    "                if (right[j-1][1] + r[j][0] - right[j-1][0])<r[j][1]:\n",
    "                    right[j] = right[j-1]\n",
    "                else:\n",
    "                    right[j] = r[j]\n",
    "        def f(arr1, arr2, a, b):\n",
    "            x1, y1 = arr1 \n",
    "            x2, y2 = arr2 \n",
    "            y = (x2 - x1 + y1 + y2)/2 \n",
    "            b2 = x2 - b + y2 \n",
    "            a2 = x2 - a + y2 \n",
    "            a1 = a - x1 + y1 \n",
    "            b1 = b - x1 + y1 \n",
    "            if a1>=a2:\n",
    "                return a2 \n",
    "            if b1<=b2:\n",
    "                return b1 \n",
    "            return y \n",
    "        ans = 0 \n",
    "        for j in range(n):\n",
    "            tmp = f(right[j], left[j], r[j][0], r[j][0])\n",
    "            ans = max(ans, tmp)\n",
    "            if j>=1:\n",
    "                if r[j][0] - r[j-1][0] > 1:\n",
    "                    tmp = f(right[j-1], left[j], r[j-1][0]+1, r[j][0]-1)\n",
    "                    ans = max(ans, tmp)\n",
    "        return int(ans)\n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxBuilding(self, n: int, restrictions: List[List[int]]) -> int:\n",
    "        stack = []\n",
    "        restrictions.append([1, 0])\n",
    "        restrictions.sort()\n",
    "        for ind, res in enumerate(restrictions):\n",
    "            heapq.heappush(stack, [res[1], ind])\n",
    "        vi = {}\n",
    "        while stack:\n",
    "            r, ind = heapq.heappop(stack)\n",
    "            i = restrictions[ind][0]\n",
    "            if i not in vi:\n",
    "                vi[i] = r\n",
    "\n",
    "                if ind - 1 >= 0:\n",
    "                    t = restrictions[ind-1][0]\n",
    "                    if t not in vi:\n",
    "                        heapq.heappush(stack, [min(r+i-t, restrictions[ind-1][1]) ,ind-1])\n",
    "                if ind + 1 < len(restrictions):\n",
    "                    t = restrictions[ind+1][0]\n",
    "                    if t not in vi:\n",
    "                        heapq.heappush(stack, [min(r+t-i, restrictions[ind+1][1]) ,ind+1])\n",
    "        ans = vi[restrictions[-1][0]] + n - restrictions[-1][0]\n",
    "        for i in range(len(restrictions)-1):\n",
    "            d = restrictions[i+1][0] - restrictions[i][0]\n",
    "            k1 = vi[restrictions[i+1][0]]\n",
    "            k0 = vi[restrictions[i][0]]\n",
    "            a = (d+k1-k0) // 2\n",
    "            ans = max(ans, k0+a)\n",
    "        return ans\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "# 2023-09-23 15:25:53\n",
    "class Solution:\n",
    "    def maxBuilding(self, n: int, restrictions: List[List[int]]) -> int:\n",
    "        mp = {i: v for i, v in restrictions}\n",
    "        mp[1] = 0\n",
    "        if n not in mp:\n",
    "            mp[n] = n - 1\n",
    "\n",
    "        q = sorted(mp.items())\n",
    "\n",
    "        left = defaultdict(int)\n",
    "\n",
    "        for (x, a), (y, b) in pairwise(q):\n",
    "            left[y] = min(b, left[x] + y - x)\n",
    "\n",
    "        m = len(q)\n",
    "        # print(left)\n",
    "\n",
    "        for i in range(1, m - 1)[::-1]:\n",
    "            x, a = q[i]\n",
    "            y, b = q[i + 1]\n",
    "            left[x] = min(left[x], left[y] + y - x)\n",
    "\n",
    "        # print(left)\n",
    "        res = 0\n",
    "        for (x, _), (y, _) in pairwise(q):\n",
    "            d = max(left[x], left[y])\n",
    "            dis = y - x - (d - min(left[x], left[y])) - 1\n",
    "            res = max(res, d + (dis + 1) // 2)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxBuilding(self, n: int, restrictions: List[List[int]]) -> int:\n",
    "        hq=[[0,1]]\n",
    "        maxh=[]\n",
    "        mp=defaultdict(bool)\n",
    "        bi=[1]\n",
    "        for idx,rstr in enumerate(restrictions):\n",
    "            heapq.heappush(hq,[rstr[1],rstr[0]])\n",
    "            bisect.insort(bi,rstr[0])\n",
    "        print(hq)\n",
    "        while len(hq)!=0:\n",
    "            t=heapq.heappop(hq)\n",
    "            if(mp[t[1]]):\n",
    "                continue\n",
    "            mp[t[1]]=True\n",
    "            h=t[0]\n",
    "            maxh.append([t[1],h])\n",
    "            right=bisect.bisect_left(bi,t[1])+1\n",
    "            left=right-2\n",
    "            if right<len(bi) and right>=0:\n",
    "                heapq.heappush(hq,[bi[right]-t[1]+h,bi[right]])\n",
    "            if left<len(bi) and left>=0:\n",
    "                heapq.heappush(hq,[t[1]-bi[left]+h,bi[left]])\n",
    "        maxh=sorted(maxh)\n",
    "        print(maxh)\n",
    "        res=0\n",
    "        for i in range(len(maxh)-1):\n",
    "            x=min(maxh[i][1],maxh[i+1][1])\n",
    "            y=max(maxh[i][1],maxh[i+1][1])\n",
    "            l=abs(maxh[i+1][0]-maxh[i][0])\n",
    "            res=max(res,y+(l-y+x)//2)\n",
    "            \n",
    "        res=max(res,maxh[-1][1]+n-maxh[-1][0])\n",
    "        return res"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
